package demo_leetcode_day;

/*
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
示例 1:
输入: num1 = "2", num2 = "3"
输出: "6"
示例 2:
输入: num1 = "123", num2 = "456"
输出: "56088"
说明：
num1 和 num2 的长度小于110。
num1 和 num2 只包含数字 0-9。
num1 和 num2 均不以零开头，除非是数字 0 本身。
不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。
*/

import java.util.Stack;

public class demo_20200813 {
    public static void main(String[] args) {
        System.out.println(new Solution().multiply("0000100000",
                "1"));
    }

    static class Solution {
        final int DEFF = 48;

        public String multiply(String num1, String num2) {
            if (null == num1 || null == num2) return "";
            Stack<String> stackSum = new Stack<String>();
            for (int i = num2.length() - 1; i >= 0; i--) {
                stackSum.push(multiplyChar(num1, num2.charAt(i)));
            }
            // 相加
            StringBuffer strRet = new StringBuffer(Math.max(num1.length(), num2.length()) * 2);
            while (!stackSum.isEmpty()) {
                strAdd(strRet, stackSum.pop());
            }
            return strRet.toString();
        }

        // 字符串和个位字符乘积结果
        private String multiplyChar(String num, char c) {
            Stack<Integer> stack = new Stack<Integer>();
            for (int i = 0; i < num.length(); i++) {
                stack.push((num.charAt(i) - DEFF) * (c - DEFF));
            }
            // 累计int相加
            StringBuffer strRet = new StringBuffer(num.length() * 2);
            int adding = 0; // 进位
            while (!stack.isEmpty()) {
                int number = stack.pop();
                strRet.insert(0, (number + adding) % 10);
                adding = (number + adding) / 10;
            }
            if (adding > 0) {
                strRet.insert(0, adding);
            }
            while (strRet.length() > 1 && strRet.charAt(0) == '0'){
                strRet.deleteCharAt(0);
            }
            return strRet.toString();
        }

        // 字符串相加
        private void strAdd(StringBuffer strRet, String strAdd) {
            if(!(strRet.length() == 1 && strRet.charAt(0) == '0')) strRet.append("0");
            int adding = 0; // 进位
            for (int i = 0; i < Math.max(strRet.length(),strAdd.length()) || adding != 0; i++) {
                if (strRet.length() <= i) strRet.insert(0, 0);
                int num = getCharInt(strRet, strRet.length() - 1 - i, 0 ) +
                          getCharInt(strAdd, strAdd.length() - 1 - i, 0 ) +
                          adding;
                strRet.setCharAt(strRet.length() - 1 - i, (char) (num % 10 + DEFF));
                adding = num / 10;
            }
        }
        // 取得对应值
        private int getCharInt(CharSequence str,int index, int def){
            if(index < 0 || str.length() <= index) return def;
            return str.charAt(index) - DEFF;
        }
    }
}
